- Title
- Linear-time superbubble identification algorithm for genome assembly
- Creator
- Brankovic, Ljiljana; Iliopoulos, Costas S.; Kundu, Ritu; Mohamed, Manal; Pissis, Solon P.; Vayani, Fatima
- Relation
- Theoretical Computer Science Vol. 609, Issue January 2016, Part 2, p. 374-383
- Publisher Link
- http://dx.doi.org/10.1016/j.tcs.2015.10.021
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2016
- Description
- DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble. In this paper, we propose an O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlogm)-time algorithm by Sung et al.
- Subject
- genome assembly; de Bruijn graphs; superbubble
- Identifier
- http://hdl.handle.net/1959.13/1321409
- Identifier
- uon:24351
- Identifier
- ISSN:0304-3975
- Language
- eng
- Reviewed
- Hits: 3048
- Visitors: 3006
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|